package com.xyj.week02;

import com.xyj.week01.Node;

/**
 * 给一个x，将链表中所有小于x的放在x左边，大于等于x的放在右边，不改变原有元素的相对顺序
 */
public class T8 {


    public static void main(String[] args) {
        //初始化链表
        Node node = new Node(4);
        Node node1 = new Node(2);
        Node node2 = new Node(1);
        Node node3 = new Node(6);
        Node node4 = new Node(8);
        node.next=node1;
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        //操作前
        Node head=node;
        System.out.println("操作前");
        while (head!=null){
            System.out.println(head);
            head=head.next;
        }
        System.out.println("操作后");
        Node nodeByX = getNodeByX(node, 4);
        while (nodeByX!=null){
            System.out.println(nodeByX);
            nodeByX=nodeByX.next;
        }


    }

    public static Node getNodeByX(Node head,int x){
        Node one=head;
        Node left=new Node(-1);
        Node me=left;
        Node right=new Node(-1);
        Node you=right;
        while(head!=null){
            if (head.value<x){
                //如果小于x的话放在左边链表
                left.next=head;
                left=left.next;
            }else{
                //放右边链表
                right.next=head;
                right=right.next;
            }
            head=head.next;
        }
        if (left.next==null){
            return one;
        }
        //断开右边链表的指针
        right.next=null;
        //左边链表指向右边链表
        left.next=you.next;
        return me.next;

    }
}
